class Solution:
    def bulbSwitch(self, n: int) -> int:
        """会超时"""
        res_list = [1] * n
        for i in range(1, n):
            for j in range(i, n, i+1):
                res_list[j] = not res_list[j]
        return sum(res_list)


class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(n ** 0.5)


a = Solution()
print(a.bulbSwitch(4))
print(a.bulbSwitch(3))  # 1
print(a.bulbSwitch(0))  # 0
